Typical communications networks normally employ several independent computing stations that communicate with each other according to a predefined scheme, usually under a centralized control. By way of example, in the telephone transmission art, groups of subscribers are routed to a local office. At the local offices the various subscription lines are multiplexed into trunks and are connected with various regional, sectional and primary toll centers. The various centers are interconnected forming a network of centers. Efficient routing of user transmissions is accomplished by monitoring the operational loads of the various centers and redirecting trunk transmissions to maximize network throughput. Various routing schemes are used, one of which involves the use of a central processor. In the central processor scheme, a single control processor monitors the networks centers and directs transmissions through the trunk network so as to maximize the network's throughput while still maintaining transmission quality. Routing schemes which employ a central control processor are efficient, provided that the network does not become too large or heavily used.
Another application of communication networks is found in the cellular mobile telephone art. Cellular technology employs cells which are transmitters and receivers. These cells are placed throughout a large geographic area such that a network of cells is formed. Each cell is capable of receiving or transmitting information from or to any mobile telephone user found within the cell's prescribed territory. All cells within a common grouping communicate their transmissions via trunks to a central Mobile Telecommunications Switching Office (MTSO). From the MTSO, the transmissions are fed into the telephone network. Because the cellular scheme typically involves the use of a central communications office (MTSO), it suffers from drawbacks similar to those found in the telephone transmission art. Consequently, in high use areas the available channels are crowded and the waiting lists for future subscribers are long. Also, communication schemes designed around a single controller are inherently vulnerable because the entire communication systems fails if the central controller is not functional.
The previous examples are typical of applications employing communication systems utilizing a central controller. In some applications it is highly desirable to eliminate the central controller and spread the control responsibilities among a plurality of dispersed intelligent control systems. One application where it is highly desirable to eliminate a central controller is in communication systems that require exceptionally high reliability, such as satellite communication and military communication systems. An isolated failure at one or more control stations in such a system normally will not compromise the integrity of the entire system.
Another application where a decentralized communication scheme is highly advantageous is in expansive communications networks where a single central communications controller can not operate quickly enough to process the necessary routing algorithms in order to effect timely and efficient transfer of information through the network of control stations. When implementing a conventional communications system, the central controller is always designed with sufficient capacity to perform its necessary functions. Normally, in addition to the capacity it necessarily needs, the controller typically possesses excess capacity to accommodate future system needs. As new control stations are appended to the base system, the capacity of the central controller is taxed to a larger and larger degree. The additional taxing on the controller is not directly proportional to the ratio of the additional control systems to the total number of control systems, but rather such taxing grows exponentially and is therefore sometimes referred to as combinatorial explosion. As additional control stations are added, a point is reached when the central controller becomes over taxed and can no longer satisfactorily perform its necessary tasks. By way of example, consider an algorithm which will solve all scheduling problems. With this algorithm it is possible to associate a function KE.sup.P such that for all possibilities P (where P equals the total number of control stations) there are KE.sup.P steps the algorithm must process in order to produce a schedule (i.e. best route available through the network). The exact value of the mathematical constant K is immaterial, because the function KE.sup.P grows too fast, regardless of the value of K, to solve problems with any substantial P by using a central controller. Much work has been done in an attempt to overcome the combinatorial explosion problem as it relates to scheduling, but in general the problem has been thought to be intractable.